{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Check if Move is Legal"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #enumeration #matrix"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #枚举 #矩阵"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: checkMove"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #检查操作是否合法"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个下标从&nbsp;<strong>0</strong>&nbsp;开始的&nbsp;<code>8 x 8</code> 网格&nbsp;<code>board</code>&nbsp;，其中&nbsp;<code>board[r][c]</code>&nbsp;表示游戏棋盘上的格子&nbsp;<code>(r, c)</code>&nbsp;。棋盘上空格用&nbsp;<code>'.'</code>&nbsp;表示，白色格子用&nbsp;<code>'W'</code>&nbsp;表示，黑色格子用&nbsp;<code>'B'</code>&nbsp;表示。</p>\n",
    "\n",
    "<p>游戏中每次操作步骤为：选择一个空格子，将它变成你正在执行的颜色（要么白色，要么黑色）。但是，<strong>合法 </strong>操作必须满足：涂色后这个格子是 <strong>好线段的一个端点</strong>&nbsp;（好线段可以是水平的，竖直的或者是对角线）。</p>\n",
    "\n",
    "<p><strong>好线段</strong>&nbsp;指的是一个包含 <strong>三个或者更多格子（包含端点格子）</strong>的线段，线段两个端点格子为 <strong>同一种颜色</strong>&nbsp;，且中间剩余格子的颜色都为 <strong>另一种颜色</strong>&nbsp;（线段上不能有任何空格子）。你可以在下图找到好线段的例子：</p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/07/22/goodlines5.png\" style=\"width: 500px; height: 312px;\" />\n",
    "<p>给你两个整数&nbsp;<code>rMove</code> 和&nbsp;<code>cMove</code>&nbsp;以及一个字符&nbsp;<code>color</code>&nbsp;，表示你正在执行操作的颜色（白或者黑），如果将格子&nbsp;<code>(rMove, cMove)</code>&nbsp;变成颜色&nbsp;<code>color</code>&nbsp;后，是一个&nbsp;<strong>合法</strong>&nbsp;操作，那么返回&nbsp;<code>true</code>&nbsp;，如果不是合法操作返回&nbsp;<code>false</code>&nbsp;。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/07/10/grid11.png\" style=\"width: 350px; height: 350px;\" /></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>board = [[\".\",\".\",\".\",\"B\",\".\",\".\",\".\",\".\"],[\".\",\".\",\".\",\"W\",\".\",\".\",\".\",\".\"],[\".\",\".\",\".\",\"W\",\".\",\".\",\".\",\".\"],[\".\",\".\",\".\",\"W\",\".\",\".\",\".\",\".\"],[\"W\",\"B\",\"B\",\".\",\"W\",\"W\",\"W\",\"B\"],[\".\",\".\",\".\",\"B\",\".\",\".\",\".\",\".\"],[\".\",\".\",\".\",\"B\",\".\",\".\",\".\",\".\"],[\".\",\".\",\".\",\"W\",\".\",\".\",\".\",\".\"]], rMove = 4, cMove = 3, color = \"B\"\n",
    "<b>输出：</b>true\n",
    "<b>解释：</b>'.'，'W' 和 'B' 分别用颜色蓝色，白色和黑色表示。格子 (rMove, cMove) 用 'X' 标记。\n",
    "以选中格子为端点的两个好线段在上图中用红色矩形标注出来了。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/07/10/grid2.png\" style=\"width: 350px; height: 351px;\" /></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>board = [[\".\",\".\",\".\",\".\",\".\",\".\",\".\",\".\"],[\".\",\"B\",\".\",\".\",\"W\",\".\",\".\",\".\"],[\".\",\".\",\"W\",\".\",\".\",\".\",\".\",\".\"],[\".\",\".\",\".\",\"W\",\"B\",\".\",\".\",\".\"],[\".\",\".\",\".\",\".\",\".\",\".\",\".\",\".\"],[\".\",\".\",\".\",\".\",\"B\",\"W\",\".\",\".\"],[\".\",\".\",\".\",\".\",\".\",\".\",\"W\",\".\"],[\".\",\".\",\".\",\".\",\".\",\".\",\".\",\"B\"]], rMove = 4, cMove = 4, color = \"W\"\n",
    "<b>输出：</b>false\n",
    "<b>解释：</b>虽然选中格子涂色后，棋盘上产生了好线段，但选中格子是作为中间格子，没有产生以选中格子为端点的好线段。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>board.length == board[r].length == 8</code></li>\n",
    "\t<li><code>0 &lt;= rMove, cMove &lt; 8</code></li>\n",
    "\t<li><code>board[rMove][cMove] == '.'</code></li>\n",
    "\t<li><code>color</code>&nbsp;要么是&nbsp;<code>'B'</code> 要么是&nbsp;<code>'W'</code>&nbsp;。</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [check-if-move-is-legal](https://leetcode.cn/problems/check-if-move-is-legal/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [check-if-move-is-legal](https://leetcode.cn/problems/check-if-move-is-legal/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[\".\",\".\",\".\",\"B\",\".\",\".\",\".\",\".\"],[\".\",\".\",\".\",\"W\",\".\",\".\",\".\",\".\"],[\".\",\".\",\".\",\"W\",\".\",\".\",\".\",\".\"],[\".\",\".\",\".\",\"W\",\".\",\".\",\".\",\".\"],[\"W\",\"B\",\"B\",\".\",\"W\",\"W\",\"W\",\"B\"],[\".\",\".\",\".\",\"B\",\".\",\".\",\".\",\".\"],[\".\",\".\",\".\",\"B\",\".\",\".\",\".\",\".\"],[\".\",\".\",\".\",\"W\",\".\",\".\",\".\",\".\"]]\\n4\\n3\\n\"B\"', '[[\".\",\".\",\".\",\".\",\".\",\".\",\".\",\".\"],[\".\",\"B\",\".\",\".\",\"W\",\".\",\".\",\".\"],[\".\",\".\",\"W\",\".\",\".\",\".\",\".\",\".\"],[\".\",\".\",\".\",\"W\",\"B\",\".\",\".\",\".\"],[\".\",\".\",\".\",\".\",\".\",\".\",\".\",\".\"],[\".\",\".\",\".\",\".\",\"B\",\"W\",\".\",\".\"],[\".\",\".\",\".\",\".\",\".\",\".\",\"W\",\".\"],[\".\",\".\",\".\",\".\",\".\",\".\",\".\",\"B\"]]\\n4\\n4\\n\"W\"']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkMove(self, board: List[List[str]], rMove: int, cMove: int, color: str) -> bool:\n",
    "        # 又长又臭的阅读理解题\n",
    "        # 好线段是最小长为3的，只有两个端点颜色一致，其余都是不行的\n",
    "        m, n = len(board), len(board[0])\n",
    "        candiates = [(i, j) for i in range(m) for j in range(n) if board[i][j] == color]\n",
    "\n",
    "        def check(x, y, u, v):\n",
    "            if not (abs(x-u) == abs(y-v) > 1 or x == u or y == v):\n",
    "                return False\n",
    "            mid_color = 'W' if color == 'B' else 'B'\n",
    "            dx = 1 if u - x > 0 else (0 if u - x == 0 else -1)\n",
    "            dy = 1 if v - y > 0 else (0 if v - y == 0 else -1)\n",
    "            x += dx\n",
    "            y += dy\n",
    "            cnt = 0\n",
    "            while not (x == u and y == v):\n",
    "                if board[x][y] != mid_color:\n",
    "                    return False\n",
    "                cnt += 1\n",
    "                x += dx\n",
    "                y += dy\n",
    "            return cnt > 0\n",
    "\n",
    "        for x, y in candiates:\n",
    "            if check(x, y, rMove, cMove):\n",
    "                return True\n",
    "     \n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkMove(self, board: List[List[str]], rMove: int, cMove: int, color: str) -> bool:\n",
    "        dirs = ((-1, 0), (1, 0), (0, 1), (0, -1), (-1, -1), (1, 1), (-1, 1), (1, -1))\n",
    "        color2 = 'B' if color == 'W' else 'W'\n",
    "        for dx, dy in dirs:\n",
    "            x, y = rMove, cMove\n",
    "            while 0 <= x + dx < 8 and 0 <= y + dy < 8 and board[x + dx][y + dy] == color2:\n",
    "                x += dx\n",
    "                y += dy\n",
    "                \n",
    "            if (x != rMove or y != cMove) and 0 <= x + dx < 8 and 0 <= y + dy < 8 and board[x + dx][y + dy] == color:\n",
    "                # print(dx, dy)\n",
    "                return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkMove(self, board: List[List[str]], rMove: int, cMove: int, color: str) -> bool:\n",
    "        # 判断每个方向是否存在以操作位置为起点的好线段\n",
    "        def check(dx: int, dy: int) -> bool:\n",
    "            x, y = rMove + dx, cMove + dy\n",
    "            step = 1   # 当前遍历到的节点序号\n",
    "            while 0 <= x < 8 and 0 <= y < 8:\n",
    "                if step == 1:\n",
    "                    # 第一个点必须为相反颜色\n",
    "                    if board[x][y] == \".\" or board[x][y] == color:\n",
    "                        return False\n",
    "                else:\n",
    "                    # 好线段中不应存在空格子\n",
    "                    if board[x][y] == \".\":\n",
    "                        return False\n",
    "                    # 遍历到好线段的终点，返回 true\n",
    "                    if board[x][y] == color:\n",
    "                        return True\n",
    "                step += 1\n",
    "                x += dx\n",
    "                y += dy\n",
    "            # 不存在符合要求的好线段\n",
    "            return False\n",
    "        \n",
    "        # 从 x 轴正方向开始逆时针枚举 8 个方向\n",
    "        dx = [1, 1, 0, -1, -1, -1, 0, 1]   # 行改变量\n",
    "        dy = [0, 1, 1, 1, 0, -1, -1, -1]   # 列改变量\n",
    "        for k in range(8):\n",
    "            if check(dx[k], dy[k]):\n",
    "                return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkMove(self, board: List[List[str]], rMove: int, cMove: int, color: str) -> bool:\n",
    "        # 判断每个方向是否存在以操作位置为起点的好线段\n",
    "        def check(dx: int, dy: int) -> bool:\n",
    "            x, y = rMove + dx, cMove + dy\n",
    "            step = 1   # 当前遍历到的节点序号\n",
    "            while 0 <= x < 8 and 0 <= y < 8:\n",
    "                if step == 1:\n",
    "                    # 第一个点必须为相反颜色\n",
    "                    if board[x][y] == \".\" or board[x][y] == color:\n",
    "                        return False\n",
    "                    else:\n",
    "                        pass\n",
    "                else:\n",
    "                    # 好线段中不应存在空格子\n",
    "                    if board[x][y] == \".\":\n",
    "                        return False\n",
    "                    # 遍历到好线段的终点，返回 true\n",
    "                    if board[x][y] == color:\n",
    "                        return True\n",
    "                    else:\n",
    "                        pass\n",
    "                step += 1\n",
    "                x += dx\n",
    "                y += dy\n",
    "            # 不存在符合要求的好线段\n",
    "            return False\n",
    "        \n",
    "        # 从 x 轴正方向开始逆时针枚举 8 个方向\n",
    "        dx = [1, 1, 0, -1, -1, -1, 0, 1]   # 行改变量\n",
    "        dy = [0, 1, 1, 1, 0, -1, -1, -1]   # 列改变量\n",
    "        for k in range(8):\n",
    "            if check(dx[k], dy[k]):\n",
    "                return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkMove(self, board: List[List[str]], rMove: int, cMove: int, color: str) -> bool:\n",
    "        def check(dx,dy):\n",
    "            x,y = rMove+dx,cMove+dy\n",
    "            step = 1    #当前遍历到的节点序列\n",
    "            while 0<= x < 8 and 0<= y < 8:\n",
    "                if step == 1:\n",
    "                    # 第一个点必须为相反颜色\n",
    "                    if board[x][y] == \".\" or board[x][y] == color:\n",
    "                        return False\n",
    "                else:\n",
    "                    #判断好线段中没有空格子\n",
    "                   if board[x][y] == '.':\n",
    "                       return False\n",
    "                    # 遍历到好线段的终点，返回 true\n",
    "                   if  board[x][y] == color:\n",
    "                       return True\n",
    "                step += 1\n",
    "                x += dx\n",
    "                y += dy\n",
    "            return False\n",
    "\n",
    "        dx = [1, 1, 0, -1, -1, -1, 0, 1]  # 行改变量\n",
    "        dy = [0, 1, 1, 1, 0, -1, -1, -1]  # 列改变量\n",
    "        for k in range(8):\n",
    "            if check(dx[k], dy[k]):\n",
    "                return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkMove(self, board: List[List[str]], rMove: int, cMove: int, color: str) -> bool:\n",
    "        for i in range(-1, 2):\n",
    "            for j in range(-1, 2):\n",
    "                d = 1\n",
    "                while 0 <= rMove + i * d < 8 and 0 <= cMove + j * d < 8 and board[rMove + i * d][cMove + j * d] != \".\":\n",
    "                    if board[rMove + i * d][cMove + j * d] == color:\n",
    "                        if d != 1:\n",
    "                            return True\n",
    "                        else:\n",
    "                            break\n",
    "                    d += 1\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkMove(self, board: List[List[str]], rMove: int, cMove: int, color: str) -> bool:\n",
    "        dirs = [(1, 0), (-1, 0), (0, 1), (0, -1),\n",
    "               (1, 1), (-1, -1), (1, -1), (-1, 1)]\n",
    "        for dr, dc in dirs:\n",
    "            i = rMove + dr\n",
    "            j = cMove + dc\n",
    "            count = 1\n",
    "            while 0 <= i < 8 and 0 <= j < 8:\n",
    "                count += 1\n",
    "                if board[i][j] == \".\": # “。不能是好线段的一部分，中间只能是另外一种颜色\n",
    "                    break\n",
    "                if board[i][j] == color: # cell becomes the \"endpont\" of a good line\n",
    "                    if count < 3:\n",
    "                        break\n",
    "                    else:\n",
    "                        return True\n",
    "                i += dr\n",
    "                j += dc\n",
    "        return False\n",
    "\n",
    "\n",
    "# class Solution:\n",
    "#     def checkMove(self, board: List[List[str]], r: int, c: int, color: str) -> bool:\n",
    "#         dirs = [(0, 1), (0, -1), (1, 0), (-1, 0), (1, 1), (-1, -1), (1, -1), (-1, 1)]\n",
    "#         for dr, dc in dirs:\n",
    "#             size = 1 # cell (r, c)   \n",
    "#             i, j = r + dr, c + dc\n",
    "#             while 0 <= i < 8 and 0 <= j < 8: # still in bound\n",
    "#                 size += 1 # cell (i, j)\n",
    "#                 if (board[i][j] == '.'):\n",
    "#                     break \n",
    "#                 # A good line is a line of three or more cells where the endpoints of the line are one color\n",
    "#                 if size < 3 and board[i][j] == color: # [b, b, b]\n",
    "#                     break\n",
    "#                 if board[i][j] == color:\n",
    "#                     return True    \n",
    "#                 i += dr\n",
    "#                 j += dc\n",
    "#         return False\n",
    "                    \n",
    "\"\"\"\n",
    "\n",
    "Q1: Why size is initialized to 2?\n",
    "A1: We actually check the cells starting from the 2nd one, and the first one is the cell we are allowed to change color.\n",
    "\n",
    "\n",
    "Starting from the given cell, check if any of the 8 directions has a good line.\n",
    "\n",
    "For each direction:\n",
    "Check if any of the neighbors is empty, if yes, break; otherwise, keep checking till encounter a cell of same color, return true if size no less than 3, otherwise break.\n",
    "\n",
    "\n",
    "https://leetcode.com/problems/check-if-move-is-legal/discuss/1389273/JavaPython-3Check-8-directions.\n",
    "\"\"\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkMove(self, board: List[List[str]], rMove: int, cMove: int, color: str) -> bool:\n",
    "        m, n = len(board), len(board[0])\n",
    "        col = {'W':'B', 'B':'W'}\n",
    "        for i in (-1, 0, 1):\n",
    "            for j in (-1, 0, 1):\n",
    "                r, c = rMove + i , cMove + j\n",
    "                step = 1\n",
    "                while 0<=r<m and 0<=c<n and board[r][c] == col[color]:\n",
    "                    r += i \n",
    "                    c += j\n",
    "                    step += 1\n",
    "                if step > 1 and 0<=r<m and 0<=c<n and board[r][c] == color:\n",
    "                    return True\n",
    "                # print(r, c, board[r][c])\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkMove(self, board: List[List[str]], rMove: int, cMove: int, color: str) -> bool:\n",
    "        dirx, diry = [1,1,1,0,-1,-1,-1,0], [1,0,-1,-1,-1,0,1,1]\n",
    "        m, n = len(board), len(board[0])\n",
    "        board[rMove][cMove] = color\n",
    "        for i in range(8):\n",
    "            nxtx, nxty = rMove + dirx[i], cMove + diry[i]\n",
    "            cando = False\n",
    "            re = 0\n",
    "            while(nxtx >= 0 and nxtx < m and nxty >=0 and nxty < n):\n",
    "                if(re == 0 and board[nxtx][nxty] == board[rMove][cMove]):\n",
    "                    break\n",
    "                if board[nxtx][nxty] == '.':\n",
    "                    break\n",
    "                if board[nxtx][nxty] != board[rMove][cMove] and board[nxtx][nxty] != '.':\n",
    "                    re = 1\n",
    "                if(re == 1 and board[nxtx][nxty] == board[rMove][cMove]):\n",
    "                    cando = True\n",
    "                    break\n",
    "                nxtx, nxty = nxtx + dirx[i], nxty + diry[i]\n",
    "            if cando:\n",
    "                return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkMove(self, board: List[List[str]], rMove: int, cMove: int, color: str) -> bool:\n",
    "        # 又长又臭的阅读理解题\n",
    "        # 好线段是最小长为3的，只有两个端点颜色一致，其余都是不行的\n",
    "        m, n = len(board), len(board[0])\n",
    "        candiates = [(i, j) for i in range(m) for j in range(n) if board[i][j] == color]\n",
    "\n",
    "        def check(x, y, u, v):\n",
    "            if not (abs(x-u) == abs(y-v) > 1 or x == u or y == v):\n",
    "                return False\n",
    "            mid_color = 'W' if color == 'B' else 'B'\n",
    "            dx = 1 if u - x > 0 else (0 if u - x == 0 else -1)\n",
    "            dy = 1 if v - y > 0 else (0 if v - y == 0 else -1)\n",
    "            x += dx\n",
    "            y += dy\n",
    "            cnt = 0\n",
    "            while not (x == u and y == v):\n",
    "                if board[x][y] != mid_color:\n",
    "                    return False\n",
    "                cnt += 1\n",
    "                x += dx\n",
    "                y += dy\n",
    "            return cnt > 0\n",
    "\n",
    "        for x, y in candiates:\n",
    "            if check(x, y, rMove, cMove):\n",
    "                return True\n",
    "     \n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkMove(self, board: List[List[str]], rMove: int, cMove: int, color: str) -> bool:\n",
    "        # 又长又臭的阅读理解题\n",
    "        # 好线段是最小长为3的，只有两个端点颜色一致，其余都是不行的\n",
    "        m, n = len(board), len(board[0])\n",
    "        candiates = [(i, j) for i in range(m) for j in range(n) if board[i][j] == color]\n",
    "\n",
    "        def check(x, y, u, v):\n",
    "            if not (abs(x-u) == abs(y-v) > 1 or x == u or y == v):\n",
    "                return False\n",
    "            mid_color = 'W' if color == 'B' else 'B'\n",
    "            dx = 1 if u - x > 0 else (0 if u - x == 0 else -1)\n",
    "            dy = 1 if v - y > 0 else (0 if v - y == 0 else -1)\n",
    "            x += dx\n",
    "            y += dy\n",
    "            cnt = 0\n",
    "            while not (x == u and y == v):\n",
    "                if board[x][y] != mid_color:\n",
    "                    return False\n",
    "                cnt += 1\n",
    "                x += dx\n",
    "                y += dy\n",
    "            return cnt > 0\n",
    "\n",
    "        for x, y in candiates:\n",
    "            if check(x, y, rMove, cMove):\n",
    "                return True\n",
    "     \n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOVE = ((1, 0), (-1, 0), (0, 1), (0, -1), (1, -1), (-1, -1), (1, 1), (-1, 1))\n",
    "REV = {'B':'W', 'W':'B'}\n",
    "\n",
    "class Solution:\n",
    "    def checkMove(self, board: List[List[str]], rMove: int, cMove: int, color: str) -> bool:\n",
    "        for di, dj in MOVE:\n",
    "            i = rMove + di\n",
    "            j = cMove + dj\n",
    "            if not (-1<i<8 and -1<j<8) or board[i][j] == color:\n",
    "                continue\n",
    "            while -1<i<8 and -1<j<8 and board[i][j] == REV[color]:\n",
    "                i += di\n",
    "                j += dj\n",
    "            if -1<i<8 and -1<j<8 and board[i][j] == color:\n",
    "                return True\n",
    "        return False\n",
    "            \n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOVE = ((1, 0), (-1, 0), (0, 1), (0, -1), (1, -1), (-1, -1), (1, 1), (-1, 1))\n",
    "REV = {'B':'W', 'W':'B'}\n",
    "\n",
    "class Solution:\n",
    "    def checkMove(self, board: List[List[str]], rMove: int, cMove: int, color: str) -> bool:\n",
    "        for di, dj in MOVE:\n",
    "            i = rMove + di\n",
    "            j = cMove + dj\n",
    "            if not (-1<i<8 and -1<j<8) or board[i][j] == color:\n",
    "                continue\n",
    "            while -1<i<8 and -1<j<8 and board[i][j] == REV[color]:\n",
    "                i += di\n",
    "                j += dj\n",
    "            if not (-1<i<8 and -1<j<8):\n",
    "                continue\n",
    "            if board[i][j] == color:\n",
    "                return True\n",
    "        return False\n",
    "            \n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkMove(self, board: List[List[str]], rMove: int, cMove: int, color: str) -> bool:\n",
    "        dct=[[1,1],[1,-1],[-1,1],[-1,-1],[1,0],[-1,0],[0,1],[0,-1]]\n",
    "        m,n=len(board),len(board[0])\n",
    "        if color=='W':\n",
    "            cc=\"B\"\n",
    "        else:\n",
    "            cc='W'\n",
    "        for dx,dy in dct:\n",
    "            if 0<=rMove+2*dx<m and 0<=cMove+2*dy<n:\n",
    "                k=1\n",
    "                c=False\n",
    "                while 0<=rMove+k*dx<m and 0<=cMove+k*dy<n:\n",
    "                    if board[rMove+k*dx][cMove+k*dy]==cc :\n",
    "                        k+=1\n",
    "                    else:\n",
    "                        if k>1 and board[rMove+k*dx][cMove+k*dy]==color:\n",
    "                            c=True\n",
    "                        break\n",
    "                if c:\n",
    "                    return True\n",
    "        return False\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkMove(self, board: List[List[str]], rMove: int, cMove: int, color: str) -> bool:\n",
    "        # 判断每个方向是否存在以操作位置为起点的好线段\n",
    "        def check(dx: int, dy: int) -> bool:\n",
    "            x, y = rMove + dx, cMove + dy\n",
    "            step = 1   # 当前遍历到的节点序号\n",
    "            while 0 <= x < 8 and 0 <= y < 8:\n",
    "                if step == 1:\n",
    "                    # 第一个点必须为相反颜色\n",
    "                    if board[x][y] == \".\" or board[x][y] == color:\n",
    "                        return False\n",
    "                else:\n",
    "                    # 好线段中不应存在空格子\n",
    "                    if board[x][y] == \".\":\n",
    "                        return False\n",
    "                    # 遍历到好线段的终点，返回 true\n",
    "                    if board[x][y] == color:\n",
    "                        return True\n",
    "                step += 1\n",
    "                x += dx\n",
    "                y += dy\n",
    "            # 不存在符合要求的好线段\n",
    "            return False\n",
    "        \n",
    "        # 从 x 轴正方向开始逆时针枚举 8 个方向\n",
    "        dx = [1, 1, 0, -1, -1, -1, 0, 1]   # 行改变量\n",
    "        dy = [0, 1, 1, 1, 0, -1, -1, -1]   # 列改变量\n",
    "        for k in range(8):\n",
    "            if check(dx[k], dy[k]):\n",
    "                return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # * 枚举每个方向验证\n",
    "    def checkMove(self, board: List[List[str]], rMove: int, cMove: int, color: str) -> bool:\n",
    "        # 判断每个方向是否存在以操作位置为起点的好线段\n",
    "        def check(dx: int, dy: int) -> bool:\n",
    "            x, y = rMove + dx, cMove + dy\n",
    "            step = 1   # 当前遍历到的节点序号\n",
    "            while 0 <= x < 8 and 0 <= y < 8:\n",
    "                if step == 1:\n",
    "                    # 第一个点必须为相反颜色\n",
    "                    if board[x][y] == \".\" or board[x][y] == color:\n",
    "                        return False\n",
    "                else:\n",
    "                    # 好线段中不应存在空格子\n",
    "                    if board[x][y] == \".\":\n",
    "                        return False\n",
    "                        \n",
    "                    # 遍历到好线段的终点，返回 true\n",
    "                    if board[x][y] == color:\n",
    "                        return True\n",
    "\n",
    "                step += 1\n",
    "                x += dx\n",
    "                y += dy\n",
    "\n",
    "            # 不存在符合要求的好线段\n",
    "            return False\n",
    "        \n",
    "        # 从 x 轴正方向开始逆时针枚举 8 个方向\n",
    "        dx = [1, 1, 0, -1, -1, -1, 0, 1]   # 行改变量\n",
    "        dy = [0, 1, 1, 1, 0, -1, -1, -1]   # 列改变量\n",
    "        for k in range(8):\n",
    "            if check(dx[k], dy[k]):\n",
    "                return True\n",
    "\n",
    "        return False\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkMove(self, board: List[List[str]], rMove: int, cMove: int, color: str) -> bool:\n",
    "        # 又长又臭的阅读理解题\n",
    "        # 好线段是最小长为3的，只有两个端点颜色一致，其余都是不行的\n",
    "        m, n = len(board), len(board[0])\n",
    "        candiates = [(i, j) for i in range(m) for j in range(n) if board[i][j] == color]\n",
    "\n",
    "        def check(x, y, u, v):\n",
    "            if not (abs(x-u) == abs(y-v) > 1 or x == u or y == v):\n",
    "                return False\n",
    "            mid_color = 'W' if color == 'B' else 'B'\n",
    "            dx = 1 if u - x > 0 else (0 if u - x == 0 else -1)\n",
    "            dy = 1 if v - y > 0 else (0 if v - y == 0 else -1)\n",
    "            x += dx\n",
    "            y += dy\n",
    "            cnt = 0\n",
    "            while not (x == u and y == v):\n",
    "                if board[x][y] != mid_color:\n",
    "                    return False\n",
    "                cnt += 1\n",
    "                x += dx\n",
    "                y += dy\n",
    "            return cnt > 0\n",
    "\n",
    "        for x, y in candiates:\n",
    "            if check(x, y, rMove, cMove):\n",
    "                return True\n",
    "     \n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkMove(self, board: List[List[str]], rMove: int, cMove: int, color: str) -> bool:\n",
    "        # 判断每个方向是否存在以操作位置为起点的好线段\n",
    "        def check(dx: int, dy: int) -> bool:\n",
    "            x, y = rMove + dx, cMove + dy\n",
    "            step = 1   # 当前遍历到的节点序号\n",
    "            while 0 <= x < 8 and 0 <= y < 8:\n",
    "                if step == 1:\n",
    "                    # 第一个点必须为相反颜色\n",
    "                    if board[x][y] == \".\" or board[x][y] == color:\n",
    "                        return False\n",
    "                else:\n",
    "                    # 好线段中不应存在空格子\n",
    "                    if board[x][y] == \".\":\n",
    "                        return False\n",
    "                    # 遍历到好线段的终点，返回 true\n",
    "                    if board[x][y] == color:\n",
    "                        return True\n",
    "                step += 1\n",
    "                x += dx\n",
    "                y += dy\n",
    "            # 不存在符合要求的好线段\n",
    "            return False\n",
    "        \n",
    "        # 从 x 轴正方向开始逆时针枚举 8 个方向\n",
    "        dx = [1, 1, 0, -1, -1, -1, 0, 1]   # 行改变量\n",
    "        dy = [0, 1, 1, 1, 0, -1, -1, -1]   # 列改变量\n",
    "        for k in range(8):\n",
    "            if check(dx[k], dy[k]):\n",
    "                return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkMove(self, board: List[List[str]], rMove: int, cMove: int, color: str) -> bool:\n",
    "        def check(dx,dy):\n",
    "            x,y = dx + rMove,dy + cMove\n",
    "            step = 1\n",
    "            while 0<=x<8 and 0<=y<8:\n",
    "                if step == 1:\n",
    "                    if board[x][y] == \".\" or board[x][y] == color:\n",
    "                        return False\n",
    "                else:\n",
    "                    if board[x][y] == \".\":\n",
    "                        return False\n",
    "                    if board[x][y] == color:\n",
    "                        return True\n",
    "                step += 1\n",
    "                x += dx\n",
    "                y += dy\n",
    "            return False\n",
    "        dx = [0,0,-1,1,-1,1,-1,1]\n",
    "        dy = [1,-1,0,0,1,1,-1,-1]\n",
    "        for i in range(8):\n",
    "            if check(dx[i],dy[i]):\n",
    "                return True\n",
    "        return False"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
